#pragma once

template<class T>
struct AVLTreeNode
{
	AVLTreeNode<T>* _left;
	AVLTreeNode<T>* _right;
	AVLTreeNode<T>* _parent;
	T _value;
	int _bf;

	AVLTreeNode(const T& value = T())
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _value(value)
		, _bf(0)
	{}
};


// AVL: 二叉搜索树 + 平衡限制： 平衡因子绝对值不能超过1
// 平衡因子：该节点左右子树高度差(后序实现约定：右子树高度 - 左子树高度)
// 假设AVL树中的value是唯一的
template<class T>
class AVLTree
{
	typedef AVLTreeNode<T> Node;
public:
	AVLTree()
		: _root(nullptr)
	{}

	~AVLTree()
	{
		Destroy(_root);
	}

	bool Insert(const T& value)
	{
		// 1. 按照二叉搜索树的规则将新节点插入
		// 空树
		if (nullptr == _root)
		{
			_root = new Node(value);
			return true;
		}

		// 非空
		// a. 按照二叉搜索树的特性中查找带插入元素的位置，并保存其双亲
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			parent = cur;
			if (value < cur->_value)
				cur = cur->_left;
			else if (value > cur->_value)
				cur = cur->_right;
			else
				return false;
		}

		// b. 插入新节点
		cur = new Node(value);
		if (value < parent->_value)
			parent->_left = cur;
		else
			parent->_right = cur;
		cur->_parent = parent;

		// 2. 更新双亲的平衡因子
		while (parent)  // ...
		{
			// cur插入之后，肯定会影响其双亲parent的平衡因子
			if (cur == parent->_left)
				parent->_bf--;
			else
				parent->_bf++;

			// 检测parent的平衡因子是否满足AVL的特性：平衡因子的绝对值不能超过1
			if (0 == parent->_bf)
			{
				// 以双亲为根的二叉树的高度没有发生变化，则不会对parent
				// 的上层产生影响，更新终止
				break;
			}
		    else if (1 == parent->_bf || -1 == parent->_bf)
			{
				// 以parent为根的二叉树的高度增加了一层
				// 肯定会对parent的双亲形成影响，需要继续往上更新
				cur = parent;
				parent = cur->_parent;
			}
			else
			{
				// parent的平衡因子可能是2或者-2，违反了AVL树的特性
				// 就需要对以parent为根的二叉树进行旋转处理
				if (2 == parent->_bf)
				{
					// parent的右子树高，最终需要左旋转
					if (1 == cur->_bf)
						RotateLeft(parent);
					else
						RoateRL(parent);
				}
				else
				{
					// parent的左子树高，最终需要右旋转
					if (-1 == cur->_bf)
						RotateRight(parent);
					else
						RotateLR(parent);
				}

				break;
			}
		}
		
		return true;
	}

	void InOrder()
	{
		cout << "中序遍历结果：";
		InOrder(_root);
		cout << endl;
	}

	bool IsValidAVLTree()
	{
		return _IsValidAVLTree(_root);
	}

private:
	int GetHeight(Node* root)
	{
		if (nullptr == root)
			return 0;

		int leftHeight = GetHeight(root->_left);
		int rightHeight = GetHeight(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}

	bool _IsValidAVLTree(Node* root)
	{
		if (nullptr == root)
			return true;

		// 根节点
		int leftHegiht = GetHeight(root->_left);
		int rigthHegiht = GetHeight(root->_right);
		if (rigthHegiht - leftHegiht != root->_bf || abs(root->_bf) > 1)
		{
			cout << "Node:" << root->_value << endl;
			cout << rigthHegiht - leftHegiht << " " << root->_bf << endl;
			return false;
		}
			

		// 根的左子树 和 根的右子树组成
		return _IsValidAVLTree(root->_left) &&
			   _IsValidAVLTree(root->_right);
	}
	// parent:右子树高--->新节点插入到较高右子树的右侧--->O(1)
	// 画图实现
	void RotateLeft(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		// 注意：类似右单支的情况，即subRL可能会为空
		if (subRL)
			subRL->_parent = parent;

		subR->_left = parent;

		// 更新parent和subR的双亲
		Node* pparent = parent->_parent;
		parent->_parent = subR;
		subR->_parent = pparent;

		// 处理pparent
		if (nullptr == pparent)
		{
			// 说明旋转之前，parent是根节点，旋转完成之后，subR就是新的根
			_root = subR;
		}
		else
		{
			// 说明旋转之前，parent是子树，parent可能是pparent的左子树或者右子树
			if (parent == pparent->_left)
				pparent->_left = subR;
			else
				pparent->_right = subR;
		}

		// 更新parent和subR的平衡因子
		parent->_bf = subR->_bf = 0;
	}

	// 右单旋
	// parent左子树高--->新节点插入到较高左子树左侧--->O(1)
	void RotateRight(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		// 注意：类似左单支---subLR为空
		if (subLR)
			subLR->_parent = parent;

		subL->_right = parent;

		// 更新suL和parent的双亲
		Node* pparent = parent->_parent;
		parent->_parent = subL;
		subL->_parent = pparent;

		// 处理pparent
		if (nullptr == pparent)
			_root = subL;
		else
		{
			if (parent == pparent->_left)
				pparent->_left = subL;
			else
				pparent->_right = subL;
		}

		// 更新subL和parent的平衡因子
		parent->_bf = subL->_bf = 0;
	}
	
	// parent的右子树高--->新节点插入到较高右子树的左侧
	void RoateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;

		RotateRight(parent->_right);
		RotateLeft(parent);

		if (1 == bf)
			parent->_bf = -1;
		else if (-1 == bf)
			subR->_bf = 1;
	}

	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;

		RotateLeft(parent->_left);
		RotateRight(parent);

		if (1 == bf)
			subL->_bf = -1;
		else if (-1 == bf)
			parent->_bf = 1;
	}

	void InOrder(Node* root)
	{
		if (root)
		{
			InOrder(root->_left);
			cout << root->_value << " ";
			InOrder(root->_right);
		}
	}

	void Destroy(Node*& root)
	{
		if (root)
		{
			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
			root = nullptr;
		}
	}
private:
	Node* _root;
};


void TestAVLTree()
{
	// int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	AVLTree<int> t;
	for (auto e : a)
		t.Insert(e);

	t.InOrder();

	if (t.IsValidAVLTree())
		cout << "t is valid AVLTree" << endl;
	else
		cout << "t is invalid AVLTree" << endl;
}